import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // int[] nums = new int[]{0,1,0,1,1,1,0,0,1};
        // System.out.println(test.findMaxLength(nums));

        int[][] arr = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
        test.matrixBlockSum(arr, 1);
    }

    public int findMaxLength1(int[] nums) {
        /**
         * 连续数组
         * 解法：使用前缀和，暴力寻找，时间复杂度将打到O（n*n）
         * 超时*/
        // 1 预处理
        int n = nums.length;

        // 2 准备前缀和
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }

        // 3 循环一圈找到目标值（使用map记录）
        int maxLength = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                int cur = i-j;
                if(cur % 2 == 0 && (dp[i] - dp[j]) == cur/2) {
                    maxLength = Math.max(cur, maxLength);
                }
            }
        }
        return maxLength;
    }

    public int findMaxLength(int[] nums) {
        /**
         * 连续数组
         * 解法：使用前缀和，暴力寻找，时间复杂度将打到O（n*n）
         * 优化方案一：使用map从大到小索引（可能更慢）
         * 优化方案二：将所有0转换为-1，再去求和为0的最长子数组的长度
         *  突然就变得简单了，为什么？因为之前我们既要考虑长度，又要考虑元素和；
         *  而现在我们已经确定元素和，则一切就水到渠成
         * */
        // 1 预处理
        int n = nums.length;
        // -将数组中所有的0转换为-1
        for(int i = 0; i < n; i++) {
            if(nums[i] == 0) {
                nums[i] = -1;
            }
        }

        // 2 准备前缀和
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }

        // 3 循环一圈找到目标值（使用map记录）
        int maxLength = 0;
        // -Map<前缀和， 下标>
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 1; i <= n; i++) {
            // -入图
            if(!map.containsKey(dp[i-1])) {
                map.put(dp[i-1], i-1);
            }

            // -寻找
            if(map.containsKey(dp[i])) {
                maxLength = Math.max(i-map.get(dp[i]), maxLength);
            }
        }
        return maxLength;
    }

    public int[][] matrixBlockSum(int[][] mat, int k) {
        /**
         * 矩阵区域和
         * */
        // 1 预处理
        int m = mat.length;
        int n = mat[0].length;

        // -计算简易矩阵和
        int[][] dp = new int[m][n];
        // -初始化
        dp[0][0] = mat[0][0];
        for(int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + mat[0][i];
        }
        for(int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + mat[i][0];
        }
        // -填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i][j];
            }
        }
        for(int[] x: dp) {
            for(int e: x) {
                System.out.print(e + "\t");
            }
            System.out.println();
        }

        // 2 根据1求目标矩阵
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // -找到有效范围
                int x1 = Math.max(i - k, 0);
                int y1 = Math.max(j - k, 0);
                int x2 = i+k >= m ? m-1 : i+k;
                int y2 = j+k >= n ? n-1 : j+k;
                // -计算面积
                ret[i][j] = dp[x2][y2];
                if(x1 != 0) {
                    ret[i][j] -= dp[x1-1][y2];
                }
                if(y1 != 0) {
                    ret[i][j] -= dp[x2][y1-1];
                }
                if(x1 != 0 && y1 != 0) {
                    ret[i][j] += dp[x1-1][y1-1];
                }
            }
        }
        return ret;
    }
}
